package org.example.list
/**
 * 链表类，用于实现基本的链表操作。
 * 包括添加元素、删除元素、获取链表大小以及按索引获取元素等功能。
 */
class LinkedList {
    // 链表头节点，初始为 null
    private var head: Node? = null

    /**
     * 向链表末尾添加一个新元素。
     *
     * @param element 要添加的字符串元素
     */
    fun add(element: String) {
        val newNode = Node(element)

        val it = tail(head)
        if (it == null) {
            // 如果链表为空，则将新节点设为头节点
            head = newNode
        } else {
            // 将新节点链接到链表末尾
            it.next = newNode
        }
    }

    /**
     * 查找链表的最后一个节点。
     *
     * @param head 链表的头节点
     * @return 最后一个节点，如果链表为空则返回 null
     */
    private fun tail(head: Node?): Node? {
        var it: Node?

        it = head
        while (it?.next != null) {
            // 遍历链表直到找到最后一个节点
            it = it.next
        }

        return it
    }

    /**
     * 从链表中移除第一个匹配的元素。
     *
     * @param element 要移除的字符串元素
     * @return 如果成功移除元素返回 true，否则返回 false
     */
    fun remove(element: String): Boolean {
        var result = false
        var previousIt: Node? = null
        var it: Node? = head
        while (!result && it != null) {
            if (0 == element.compareTo(it.data)) {
                // 找到匹配的元素，执行移除操作
                result = true
                unlink(previousIt, it)
                break
            }
            previousIt = it
            it = it.next
        }

        return result
    }

    /**
     * 断开当前节点与链表的连接。
     *
     * @param previousIt 当前节点的前一个节点，如果是头节点则为 null
     * @param currentIt 当前要断开的节点
     */
    private fun unlink(previousIt: Node?, currentIt: Node) {
        if (currentIt == head) {
            // 如果当前节点是头节点，则将头节点指向下一个节点
            head = currentIt.next
        } else {
            // 将前一个节点的 next 指针指向当前节点的下一个节点
            previousIt?.next = currentIt.next
        }
    }

    /**
     * 获取链表中的元素数量。
     *
     * @return 链表的大小
     */
    fun size(): Int {
        var size = 0

        var it = head
        while (it != null) {
            // 遍历链表并计数
            ++size
            it = it.next
        }

        return size
    }

    /**
     * 根据索引获取链表中的元素。
     *
     * @param idx 元素的索引
     * @return 索引对应的元素值
     * @throws IndexOutOfBoundsException 如果索引超出范围
     */
    fun get(idx: Int): String {
        var index = idx
        var it = head
        while (index > 0 && it != null) {
            // 遍历链表直到找到指定索引的节点
            it = it.next
            index--
        }

        if (it == null) {
            // 如果索引超出范围，抛出异常
            throw IndexOutOfBoundsException("索引超出范围")
        }

        return it.data
    }

    /**
     * 表示链表中的节点，包含数据和指向下一个节点的引用。
     */
    private data class Node(val data: String) {
        // 指向下一个节点的引用，初始为 null
        var next: Node? = null
    }
}
